1. Field of the Invention
The present invention relates generally to a spelling and grammar checking system, and more particularly to a spelling and grammar checking system which corrects misspelled words, incorrectly-used words, and contextual and grammatical errors. The invention has particular utility in connection with machine translation systems, word processing systems, and text indexing and retrieval systems such as World Wide Web search engines.
2. Description of the Related Art
Conventional spelling correction systems, such as those found in most common word processing applications, check whether each word in a document is found in a dictionary database. When a word is not found in the dictionary, the word is flagged as being incorrectly spelled. Suggestions for replacing the incorrectly-spelled word with its correctly-spelled counterpart are then determined by inserting, deleting and/or transposing characters in the misspelled word. For example, in a sentence like My son thre a ball at me, the word thre is not correctly-spelled. Conventional spelling correction systems, such as those described in U.S. Pat. No. 4,580,241 (Kucera) and U.S. Pat. No. 4,730,269 (Kucera), suggest words such as threw, three, there and the, as possible alternatives for the misspelled word by adding and deleting characters at different locations in the misspelled word. These alternative words are then displayed to a user, who must then select one of the alternatives.
One of the drawbacks of conventional systems is that they lack the ability to suggest alternative words based on the context in which the misspelled word appears. For example, in the following three sentences, the word thre appears in different contexts and, therefore, should be corrected differently in each sentence.                My son thre a ball through the window.        He broke thre window.        He moved thre years ago.        
More specifically, in the first sentence, the incorrectly-spelled word thre should be replaced by threw. In the second sentence, the word thre should be replaced by the. In the third sentence, the word thre should be replaced by three. In spite of these differences in context, conventional spelling correction systems suggest the same list of alternative words, ranked in the same order, for all three of the foregoing sentences. For example, the spelling correction program provided in Microsoft® Word '97 suggests the following words, in the following order, for all three of the foregoing sentences: three, there, the, throe, threw.
Since conventional spelling correction systems do not rank alternative words according to context, such systems are not able to correct spelling mistakes automatically, since to do so often leads to an inordinate number of incorrectly corrected words. Rather, such systems typically use an interactive approach to correcting misspelled words. While such an approach can be effective, it is inefficient, and oftentimes very slow, particularly when large documents are involved. Accordingly, there exists a need for a spell checking system which is capable of ranking alternative words according to context, and which is also capable of automatically correcting misspelled words without significant user intervention.
Conventional spelling correction systems are also unable to correct grammatical errors in a document or other input text, particularly if those words are spelled correctly but are misused in context. By way of example, although the word too is misused in the sentence He would like too go home, conventional spelling correction systems would not change too to to, since too is correctly spelled. In this regard, grammar checking systems are available which correct improperly used words (see, e.g., U.S. Pat. No. 4,674,065 (Lange), U.S. Pat. No. 5,258,909 (Damerau), U.S. Pat. No. 5,537,317 (Schabes), U.S. Pat. No. 4,672,571 (Bass), and U.S. Pat. No. 4,847,766 (McRae)). Such systems, however, are of limited use, since they are only capable of correcting relatively short lists of predefined words. More importantly, such systems are not capable of performing grammar corrections on words that have been misspelled.
Accordingly, there exists a need for a spelling and grammar checking system which is capable of correcting words that have misused in a given context in cases where the words have been spelled incorrectly and in cases where the words have been spelled correctly.